package example2;

//155. 最小栈
public class LeetCode155 {
    public static void main(String[] args) {
        MinStack minStack = new MinStack();  // 步骤0: 初始化栈
        minStack.push(0);                    // 步骤1: 压入0
        minStack.push(1);                    // 步骤2: 压入1
        minStack.push(0);                    // 步骤3: 压入0
        System.out.println(minStack.getMin()); // 步骤4: 获取最小值，应返回0
        minStack.pop();                      // 步骤5: 弹出栈顶元素(0)
        System.out.println(minStack.getMin()); // 步骤6: 获取最小值，应返回0
        minStack.pop();                      // 步骤7: 弹出栈顶元素(1)
        System.out.println(minStack.getMin()); // 步骤8: 获取最小值，应返回0
        minStack.pop();                      // 步骤9: 弹出栈顶元素(0)，栈空
        minStack.push(-2);                   // 步骤10: 压入-2
        minStack.push(-1);                   // 步骤11: 压入-1
        minStack.push(-2);                   // 步骤12: 压入-2
        System.out.println(minStack.getMin()); // 步骤13: 获取最小值，应返回-2
        minStack.pop();                      // 步骤14: 弹出栈顶元素(-2)
        System.out.println(minStack.top());    // 步骤15: 获取栈顶元素，应返回-1
        System.out.println(minStack.getMin()); // 步骤16: 获取最小值，应返回-2
        minStack.pop();                      // 步骤17: 弹出栈顶元素(-1)
        System.out.println(minStack.getMin()); // 步骤18: 获取最小值，应返回-2
        minStack.pop();                      // 步骤19: 弹出栈顶元素(-2)，栈空
    }
}

/*
* 方法二：可以再在MinStack内部再维护一个栈，用于存储当前栈顶元素在栈中时对应的最小值，
* 这个存储最小值的辅助栈和原本的栈一同入栈和出栈，所以两个栈的元素个数始终相等，
* 要获取当前栈的最小值时只需要获取辅助栈的栈顶元素即可，每次有新元素进来时，就先将新元素
* 加入到主栈中，然后将新元素与插入之前的最小值比较得出新的最小值，将新的最小值加入到辅助栈中
* */

/**
 * 自己想的方法一，普通
 */
class MinStack {
    private int[] data;
    private int capacity;
    private int size;
    private int min;

    public MinStack() {
        this.capacity = 10;
        this.size = 0;
        this.min = 0;
        this.data = new int[capacity];
    }

    public void push(int val) {
        if(size == 0){
            min = val;
        }
        if(size == capacity){
            resize1();
        }
        if(val < min){
            min = val;
        }
        data[size] = val;
        size++;
    }

    public void pop() {
        size--;
        int temp = data[size];
        data[size] = 0;
        if(size <= capacity / 2){
            resize2();
        }
        if(temp == min){
            //不用担心索引越界，因为会限制最短长度为10，当size==0时，也min==0
            min = data[0];
            for(int i=1;i<size;i++){
                if(data[i] < min)   min = data[i];
            }
        }
    }

    public int top() {
        if(size == 0)   return 0;
        return data[size - 1];
    }

    public int getMin() {
        return min;
    }

    //扩容
    private void resize1(){
        capacity += capacity / 2;
        int[] newData = new int[capacity];
        for(int i=0;i<size;i++){
            newData[i] = data[i];
        }
        data = newData;
    }

    //缩小
    private void resize2(){
        capacity = capacity / 4 * 3;
        capacity = capacity > 10 ? capacity : 10;
        int[] newData = new int[capacity];
        for(int i=0;i<size;i++){
            newData[i] = data[i];
        }
        data = newData;
    }
}
